public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        // int[] nums = new int[]{-1,0,3,5,9,12};
        // System.out.println(test.search(nums, -10));

        int[] nums = new int[]{5,7,7,8,8,10};
        int[] retArray = test.searchRange(nums, 8);
        for(int x: retArray) {
            System.out.print(x + " ");
        }
    }

    public int search(int[] nums, int target) {
        /**
         * 朴素二分查找
         * */
        // 1 预处理
        int n = nums.length;

        // 2 朴素二分查找
        int left = 0;
        int right = n-1;
        while(left <= right) {
            // -1 找中点值
            int mid = left + (right - left)/2;
            int temp = nums[mid];
            // -2 判断
            if(temp == target) {
                return mid;
            } else if(temp < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        /**
         * 在排列数组中查找元素的第一个和最后一个位置
         * 先查左端点再查右端点
         * */
        // 1 预处理
        int n = nums.length;
        int[] retArr = new int[2];

        // 2 查找左端点
        int left = 0;
        int right = n-1;
        while(left < right) {
            // -选择左中心点，避免出现死循环
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if(left == right && nums[left] == target) {
            retArr[0] = left;
        } else {
            retArr[0] = -1;
        }

        // 3 查找右端点
        left = 0;
        right = n - 1;
        while(left < right) {
            // -选择右中心点，避免出现死循环
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if(left == right && nums[left] == target) {
            retArr[1] = left;
        } else {
            retArr[1] = -1;
        }
        
        // 4 返回值
        return retArr;
    }
}
